﻿#include "mat.h"
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <chrono>
#include <random>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Nod {
    int x, y;
    int step;
    Nod(int _x, int _y, int _stp)
    {
        x = _x;
        y = _y;
        step = _stp;
    }
};

queue<Nod>Q;

Cell::Cell() {
    val = 0;
    north = south = east = west = 0;
}

Mat::Mat() {
    init();
}

Mat::~Mat() {}

void Mat::init() {
    // 40, 25
    memset(vis, false, sizeof(vis));
    memset(mark, false, sizeof(mark));
    path.clear();
    path_bfs.clear();
    for (int i =1; i <= n; i++) {
        for (int j =1; j <= m; j++) {
            if (i & 1) mat[i][j].val =0;
            if (!(i&1) && (j & 1) == 0) mat[i][j].val = 0;
            else mat[i][j].val = 1;
        }
    }
}

// 生成mat
void Mat::generate(){
    std::random_device rd;
    std::uniform_int_distribution<int> dist(0, 9999999);
    srand(dist(rd));
    bool success = false;
    do {
        init();
        mat_maxdept = -1;
        int s = rand()%4;

        // if the m*n matrix is odd*odd, then
        if (s == 1 || s == 3) {
            //left,right
            sr = (rand()%n + 2);
            if (sr&1) sr += 1;
            if (sr == n+1) sr = sr / 2 + 1;
            sc = rand() % 2 == 1 ? m : 2;
        } else {
            // up, down
            sc = rand() % m + 2;
            if ((sc&1)) sc += 1;
            if (sc == m+2) sc = sc / 2 + 1;
            sr = rand()%2 == 1 ? n-1 : 2;
        }
        er = 0, ec = 0;
        dfs_find_path(sr, sc, 0);
        success = checker();
    } while (!success);
    path.push_back(make_pair(sr, sc));
}

void Mat::print() {

    printf("Base view\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m+1; j++) {
            if (vis[i][j]) putchar('0');
            else putchar('1');
        }
        printf("\n");
    }
}


// 深度优先搜索
void Mat::dfs_find_path(int x, int y, int dept) {

	// 随机数生成器
    std::random_device rd;
    std::uniform_int_distribution<int> dist(0, 9999999);
    if (dept > mat_maxdept) {
        er = x, ec = y;
        mat_maxdept = dept;
    }

    int cnt = 0;
    int dir[4] = {-1};
    if (isLegal(x, y-2) && mat[x][y-2].val == 0 && !vis[x][y-2] && !vis[x][y-1])
        dir[cnt++] = 0;
    if (isLegal(x+2, y) && mat[x+2][y].val == 0 && !vis[x+2][y] && !vis[x+1][y])
        dir[cnt++] = 1;
    if (isLegal(x, y+2) && mat[x][y+2].val == 0 && !vis[x][y+2] && !vis[x][y+1])
        dir[cnt++] = 2;
    if (isLegal(x-2, y) && mat[x-2][y].val == 0 && !vis[x-2][y] && !vis[x-1][y])
        dir[cnt++] = 3;
    if (!cnt) return ;
    else {
        //waste_time();
        shuffle(dir, dir+cnt, std::default_random_engine(dist(rd)));
        for (int i = 0; i < cnt; i++) {
            int xx = dx[dir[i]] + x, yy = dy[dir[i]] + y;
            if (vis[xx][yy]) return ;
            vis[xx][yy] = 1;
            mat[xx][yy].val = 0;
            if (dir[i] == 0) vis[xx][yy+1] = 1, mat[xx][yy+1].val = 0;
            if (dir[i] == 1) vis[xx-1][yy] = 1, mat[xx-1][yy].val = 0;
            if (dir[i] == 2) vis[xx][yy-1] = 1, mat[xx][yy-1].val = 0;
            if (dir[i] == 3) vis[xx+1][yy] = 1, mat[xx+1][yy].val = 0;
            dfs_find_path(xx, yy, dept+1);
        }
    }
}

// 路径记录
void Mat::path_dfs(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int xx = x + dx[i]/2, yy = y + dy[i] / 2;
        if(isLegal(xx, yy) && !mark[xx][yy] && vis[xx][yy]) {
            path.push_back(make_pair(xx, yy));
            mark[xx][yy] = 1;
            path_dfs(xx, yy);
        }
    }
}


// 宽度优先搜索
void Mat::bfs_path() {

    Nod st(sr, sc, 0);
    Q.push(st);
    memset(mark, false, sizeof(mark));
    mark[sr][sc] = true;

    while (!Q.empty()) {
        Nod now = Q.front(); Q.pop();
        path_bfs.push_back(make_pair(now.x, now.y));
        for (int i = 0; i < 4; i++) {
            int xx = now.x + dx[i] / 2, yy = now.y + dy[i] / 2;
            if (isLegal(xx, yy) && !mark[xx][yy] && vis[xx][yy]) {
                st.x = xx, st.y = yy;
                st.step = now.step + 1;
                mark[st.x][st.y] = true;
                Q.push(st);
            }
        }
    }

}

bool Mat::dfs_dir_checker(int x, int y) {
    return x ^ y;
}

bool Mat::isLegal(int x, int y) {
    return x >= 1 && y <= m && x <= n && y >= 1;
}

void Mat::waste_time() {
    int n = 0;
    while (n < 100000) n++;
}

bool Mat::checker() {
    bool fl = 0;
    for (int i = 1; i <= m; i++)
        fl |= vis[2][i];
    return fl == 1;
}

// 数据预处理
void Mat::preprocess() {
    for (int i = 1; i <= n+1; i++) {
        for (int j = 1; j <= m+1; j++) {
            if (vis[i+1][j] == 1) mat[i][j].south = 1;
            if (vis[i][j+1] == 1) mat[i][j].east  = 1;
            if (vis[i-1][j] == 1) mat[i][j].north = 1;
            if (vis[i][j-1] == 1) mat[i][j].west = 1;
        }
    }

    path_dfs(sr, sc);
    totSteps = path.size();
    bfs_path();
}

void Mat::print_vis() {

    printf("Block view:\n");
    printf("(%d, %d)-->(%d, %d)\n", sr, sc, er, ec);
    for (int i = 1; i <= n+1; i++) {
        for (int j = 1; j <= m+1; j++) {
            if (i == sr && j == sc) {
                printf("<");
                continue;
            }
            if (i == er && j == ec) {
                printf(">");
                continue;
            }
            if (vis[i][j]) printf(".");
            else printf("#");
        }
        printf("\n");
    }
}

void Mat::print_grid() {

    printf("Grid view:\n");
    printf("(%d, %d)-->(%d, %d)\n", sr, sc, er, ec);
    for (int i = 1; i <= 2*m-1; i++)
        printf("_");
    printf("\n");
    for (int i = 2; i <= n; i++) {
        printf("|");
        for (int j = 2; j <= m; j++) {
            if (mat[i][j].south == 1 && vis[i][j] == 1) {
                if (i == sr && j == sc)
                    printf("<");
                else
                    printf(" ");
            }
            else printf("_");
            if (mat[i][j].east == 1 && vis[i][j] == 1) {
                if (i == er && j == ec)
                    printf(">");
                else
                    printf(" ");
            }
            else printf("|");
        }
        printf("\n");
    }
}

void Mat::print_line() {

    printf("Line view:\n");
    printf("(%d, %d)-->(%d, %d)\n", sr, sc, er, ec);
    for (int i = 1;i <= n; i++) {
        for (int j = 1; j <= m+1; j++) {
            if (i == 1 || i == n || j == 1 || j == m+1) {
                if (i == 1 || i == n)
                    printf("-");
                else
                    printf("|");

                continue;
            }
            if (vis[i][j] == 1) {
                if (i == sr && j == sc)
                    printf("<");
                else if (i == er && j == ec)
                    printf(">");
                else
                    printf(" ");
            } else {
                if (i & 1)
                    printf("-");
                else
                    printf("|");
            }
        }
        printf("\n");
    }
}

void Mat::path_trace() {
    int cnt = 0;

    for (vector<pair<int, int> >::iterator it = path.begin(); it != path.end(); it++) {
        cout << "(" << it->first << ", " << it->second << ")";
        cnt += 1;
        if (cnt % 10 == 0) cout << endl;
    }
    cout << endl;

}

/*
 *
 *
 Test:
    Mat mp;

int main(int argc, char *argv[]) {

    //valgrind ./a.out
    mp.dfs_find_path(mp.sr, mp.sc, 0);
    printf("\n");
    mp.print();
    mp.print_vis();
    mp.preprocess();
    mp.print_grid();
    mp.print_line();


    return 0;
}
*/
